package leecode.maxbag;

public class MaxBag {
    public static void main(String[] args) {
        System.out.println("背包问题");
        int c = 4; // 总容量为10
        int n = 3; // 总个数为5
        int[] weight = {1, 4, 3};
        int[] value = {1500, 3000, 2000};
        calc(c, n, weight, value);
    }

    private static void calc(int c, int n, int[] weight, int[] value) {
        int[][] maxValue = new int[n][c + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= c; j++) {
                maxValue[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= c; j++) {
                if (i == 0) {
                    maxValue[i][j] = j >= weight[i] ? value[i] : 0;
                } else {
                    // 先存一下top值
                    int top = maxValue[i - 1][j];
                    int cur = j >= weight[i] ? (j - weight[i] > 0 ? (value[i] + maxValue[i - 1][j - weight[i]]) : value[i]) : top;
                    maxValue[i][j] = Math.max(top, cur);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= c; j++) {
                if (maxValue[i][j] >= 10) {
                    System.out.print(maxValue[i][j] + " ");
                } else {
                    System.out.print(maxValue[i][j] + "  ");
                }
            }
            System.out.println();
        }
    }
}
